Quick Index
What and Why


What is a Deque?
A deque (pronounced "deck") structure allows efficient add and remove on both ends of the structure.

Thus we do not define it as either of FIFO or LIFO.
Why a Deque?
A deque has a broad range of uses.

A few examples:

  • Tracking browser history (urls)
  • Undo-redo operations
  • Some job scheduling processes (e.g. the "a-steal" algorithm for multiple processors)
  • Any algorithms that benefit from efficient access at both ends of structure


Deque vs Stack


We may ask why not use a simple "Stack" for tracking browser history or undo-redo, and other similar problems?

The reason is we want to "work" both ends. One end for adding and removing, and the other end for trimming/pruning (removing) when list becomes oversized.

Deque vs Queue


We may have problems where we have something similar to a queue, but with variations.

For example, say we have a line of persons at the airport, movie theatre, etc. The line is queue-like, but a person with special needs or privileges might be allowed to enter the front of the line.

We use a deque for this because it models a queue just fine, but also allows efficient access on both ends, when needed.

Fundamental Operations


A deque has four core operations allowing add/remove access on both ends.

OperationNotes
addFirstAdd element to front
removeFirstRemove element from front
addLastAdd element to rear
removeLastRemove element from rear


addFirst and addLast
A deque allows adding elements to either end.
removeFirst and removeLast
A deque allows removing elements from either end.


FIFO or LIFO?


Which mode does a deque run in?


A deque is not limited to either mode. The order of elements added and removed varies for a deque.

Traversal (Iteration)


We define the default traversal for a deque to be from first to last (or front to rear). Although we could also easily iterate in the reverse direction.

By default, we would visit the example in this order:

ZZ, FF, YY, GG


ADT


See the ADT here...

References




Navigation
































Data Structures And Algorithms (DSA) (Chapter 504 - Deque)










CHAP503 < Deque > CHAP505

Chapter Top Search Site TOC